int toWeightStep(int x)
{
    if(x == 1)
        return 0;
    int step = 0;
    while(x != 1)
    {
        if(x % 2 == 0)
            x = x / 2;
        else
            x = x * 3 + 1;
        step++;
    }
    return step;
}
struct cmp
{
    bool operator()(int x, int y)
    {
        int x1 = toWeightStep(x), y1 = toWeightStep(y);
        if(x1 == y1)
            return x < y;
        return x1 < y1;
    }
};

// 记忆化搜索
unordered_map<int, int> memo;   // <i, 变成 1 的步数>
int dfs(int i)
{
    if(i == 1)
        return 0;
    
    if(memo.find(i) != memo.end())
        return memo[i];
    
    if(i % 2)   // 奇数
        return memo[i] = dfs(((i * 3) + 1) / 2) + 2;     // i 是奇数，那 i * 3 + 1 一定是偶数，偶数的话又可以除以 2 ，所以并在一起写了
    else        // 偶数
        return memo[i] = dfs(i / 2) + 1;
}

class Solution
{
public:
    int getKth(int lo, int hi, int k)
    {
        vector<int> nums(hi - lo + 1);

        iota(nums.begin(), nums.end(), lo);     // 从 lo 自增填满 nums 数组

        sort(nums.begin(), nums.end(), [&](int x, int y)
        {
            int fx = dfs(x), fy = dfs(y);
            if(fx == fy)
                return x < y;
            else
                return fx < fy;
        });
        return nums[k - 1];

        // for(int i = lo; i <= hi; i++)
        //     nums[i - lo] = i;
        // sort(nums.begin(), nums.end(), cmp());
        // return nums[k - 1];
    }
};